﻿#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>

using namespace std;




//int n;
//const int N = 1e6 + 10;
//vector<int> edges[N];
//bool st[N];
//int h[N], id;
//int ne[N * 2], e[N * 2];
//
//void add(int a, int b)
//{
//	id++;
//	e[id] = b;
//	ne[id] = h[a];
//	h[a] = id;
//
//}
//
//
//void dfs(int u)
//{
//	cout << u << " ";
//	st[u] = true;
//
//	for (auto v : edges[u])
//	{
//		if (!st[v])
//			dfs(v);
//	}
//}
//
//void test1()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		int a, b; cin >> a >> b;
//		edges[a].push_back(b);
//		edges[b].push_back(a);
//	}
//	dfs(1);
//}
//
//void dfs2(int u)
//{
//	cout << u << " ";
//	st[u] = true;
//
//	for (int i = h[u]; i; i = ne[i])
//	{
//		int v = e[i];
//		if (!st[v]) dfs2(v);
//	}
//}
//
//void test2()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		int a, b; cin >> a >> b;
//		add(a, b);
//		add(b, a);
//	}
//	dfs2(1);
//}
//
//int main()
//{
//	test2();
//	return 0;
//}



// 链式前向星
//const int N = 1e5 + 10;
//int h[N],id;
//int ne[N * 2], e[N * 2];
//
//void push(int a, int b)
//{
//	id++;
//	e[id] = a;
//	ne[id] = h[a];
//	h[a] = id;
//	
//}
//
//int main()
//{
//	int n; cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		int a, b; cin >> a >> b;
//		push(a, b);
//		push(b, a);
//
//	}
//	return 0;
//}



// 顺序存储
//const int N = 1e6 + 10;
//vector<int> edges[N];
//
//int main()
//{
//	int n; cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		int a, b; cin >> a >> b;
//		edges[a].push_back(b);
//		edges[b].push_back(a);
//	}
//	return 0;
//}


//int main()
//{
//	queue<int> q;
//	for (int i = 0; i < 10; i++) q.push(i);
//	for (int i = 0; i < 10; i++)
//	{
//		cout << q.front() << " ";
//		q.pop();
//	}
//
//	//cout << q.size() << endl;
//	//cout << q.empty() << endl;
//
//	return 0;
//}


//const int N = 1e6 + 10;
//int h, t;
//int q[N];
//
//
//void print()
//{
//	for (int i = h + 1; i <= t; i++)
//	{
//		cout << q[i] << " " ;
//	}
//	cout << endl;
//}
//// 入队
//void push(int x)
//{
//	q[++t] = x;
//}
//
//// 出队
//void pop()
//{
//	++h;
//}
//
//// 队头
//int head()
//{
//	return q[h + 1];
//}
//
//// 队尾
//int back()
//{
//	return q[t];
//}
//
//// 判空
//bool empty()
//{
//	return h == t;
//}
//
//// 元素个数
//int size()
//{
//	return t - h;
//}
//
//
//int main()
//{
//	cout << "push:" << endl;
//	push(1);
//	print();
//	push(2);
//	print();
//	push(3);
//	print();
//	push(4);
//	print();
//
//	//cout << "pop:" << endl;
//	//pop();
//	//print();
//	//pop();
//	//print();
//	//pop();
//	//print();
//	//pop();
//	//print();
//
//	cout << head() << endl;
//	cout << back() << endl;
//
//	return 0;
//}

//const int N = 110;
//
//
//bool st[N];
//
//int main()
//{
//    string s; cin >> s;
//    stack<int> stk;
//    // 处理一遍字符串
//    for (int i = 0; i < s.size(); i++)
//    {
//        char ch = s[i];
//        int t = stk.top();
//        if (ch == '(' || ch == '[')
//            stk.push(i);
//        else
//        {
//            if (stk.empty()) continue;
//            if ((ch == ']' && s[t] == '[') || (ch == ')' && s[t] == ')'))
//            {
//                st[t] = st[i] = true;
//                stk.pop();
//            }
//        }
//    }
//
//
//    // 配对
//    string ret = "";
//    for (int i = 0; i < s.size(); i++)
//    {
//        char ch = s[i];
//        if (st[i]) {
//            ret += ch;
//            continue;
//        }
//        else if (ch == '(')
//        {
//            ret += ch;
//            ret += ')';
//        }
//        else if (ch == ')')
//        {
//            ret += '(';
//            ret += ch;
//        }
//        else if (ch == '[')
//        {
//            ret += ch;
//            ret += ']';
//        }
//        else {
//            ret += '[';
//            ret += ch;
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}




//
//#include <iostream>
//#include <stack>
//using namespace std;
//const int N = 110;
//bool st[N]; // 标记有没有匹配
//int main()
//{
//	string s; cin >> s;
//	int n = s.size();
//	stack<int> stk; // ⾥⾯存的是左括号的下标
//	string ret;
//	for (int i = 0; i < n; i++)
//	{
//		if (s[i] == '(' || s[i] == '[')
//		{
//			stk.push(i);
//		}
//		else
//		{
//			if (stk.empty()) continue;
//			char ch = s[stk.top()];
//			if ((ch == '(' && s[i] == ')') || (ch == '[' && s[i] == ']')) // 能匹配
//			{
//			st[stk.top()] = true;
//			st[i] = true;
//			stk.pop();
//			}
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		char ch = s[i];
//		if (st[i]) ret += ch;
//		else
//		{
//			// 不能匹配就要加括号
//			if (ch == '(')
//			{
//				ret += ch;
//				ret += ')';
//			}
//			else if (ch == ')')
//			{
//				ret += '(';
//				ret += ch;
//			}
//			else if (ch == '[')
//			{
//				ret += ch;
//				ret += ']';
//			}
//			else if (ch == ']')
//			{
//				ret += '[';
//				ret += ch;
//			}
//		}
//	}
//	cout << ret << endl;
//	return 0;
//}



//const int N = 1e5 + 10;
//int a[N], b[N];
//int n;
//
//int main()
//{
//	int q; cin >> q;
//	while (q--)
//	{
//		cin >> n;
//		for (int i = 1; i <= n; i++) cin >> a[i];
//		for (int i = 1; i <= n; i++) cin >> b[i];
//
//		stack<int> st;
//		int j = 1;
//		for (int i = 1; i <= n; i++)
//		{
//			st.push(a[i]);
//			while (j <= n && st.size()&& st.top() == b[j])
//			{
//				st.pop();
//				j++;
//			}
//		}
//		if (st.size()) cout << "No" << endl;
//		else cout << "Yes" << endl;
//	}
//	return 0;
//}
//

//stack<int> pushed;
//stack<int> poped;
//int main()
//{
//	int q; cin >> q;
//	while (q--)
//	{
//		bool flag = true;
//		int x; cin >> x;
//		for (int i = 0; i < x; i++)
//		{
//			int m; cin >> m;
//			pushed.push(m);
//			/*cout << poped.top() << " ";
//			if (m != poped.top())
//				flag = false;*/
//		}
//		for (int i = 0; i < x; i++)
//		{
//			cout << poped.top() << " ";
//			if(pushed.top() == pop)
//		}
//		if (flag)	cout << "Yes" << endl;
//		else cout << "No" << endl;
//
//}
//typedef unsigned long long LL;
//
//const int N = 1e6 + 10;
//int top;
//LL st[N];
//
//int main()
//{
//	int T;
//	cin >> T;
//	while (T--)
//	{
//		top = 0;
//		int n; cin >> n;
//		while (n--)
//		{
//			string op; cin >> op;
//			if (op == "push")
//			{
//				LL x; cin >> x;
//				st[++top] = x;
//			}
//			else if (op == "pop")
//			{
//				if (top == 0)
//					cout << "Empty" << endl;
//				else 
//					top--;
//			}
//			else if (op == "query")
//			{
//				if (top== 0)
//					 cout << "Anguei!" << endl;
//				else 
//					cout << st[top] << endl;
//			}
//			else{
//				cout <<  top << endl;
//			}
//		}
//	}
//	return 0;
//}

//int main()
//{
//	stack<int> st;
//	for (int i = 0; i < 10; i++)
//		st.push(i);
//	for (int i = 0; i < st.size(); i++)
//	{
//		cout << st.top() << " ";
//		st.pop();
//	}
//	return 0;
//}

//const int N = 1e5 + 10;
//int stk[N];
//int n;
//
//// 进栈
//void push(int x)
//{
//	stk[++n] = x;
//}
//
//// 出栈
//void pop()
//{
//	n--;
//}
//
//// 查找
//int top()
//{
//	return stk[n];
//}
//
//// 判空
//bool empty()
//{
//	return n == 0;
//}
//
//// 判断有效元素个数
//int size()
//{
//	return n;
//}
//
//void print()
//{
//	for (int i = 1; i <= n; i++) cout << stk[i];
//	cout << endl;
//}
//
//int main()
//{
//	cout << "push:" << endl;
//	push(1);
//	print();
//	push(2);
//	print();
//	push(3);
//	print();
//	push(4);
//	print();
//	push(5);
//	print();
//
//
//	//cout << "pop:" << endl;
//	//pop();
//	//print();
//	//pop();
//	//print();
//	//pop();
//	//print();
//	//pop();
//	//print();
//	//pop();
//	//print();
//
//	
//	//cout << "top:" << endl;
//	//cout << top() << endl;
//	//pop();
//	//cout << top() << endl;
//	//pop();
//	//cout << top() << endl;
//
//
//	//cout << "empty:" << endl;
//	//cout << empty() << endl;
//	//pop();
//	//pop();
//	//pop();
//	//pop();
//	//pop();
//	//cout << empty() << endl;
//
//	
//	cout << "size:" << endl;
//	cout << size() << endl;
//	pop();
//	cout << size() << endl;
//	pop();
//	cout << size() << endl;
//
//	return 0;
//}








